#include <cstdio>
#include <cstring>

int min( int a, int b ) { return ( a < b )?a:b; }

void getnext( char *s, int *next )
{
    int i = 1, j = -1, len = strlen( s );
    next[ 0 ] = -1;
    while ( s[ i ] )
    {
        while ( j >= 0 && s[ j + 1 ] != s[ i ] ) j = next[ j ];
        if ( s[ j + 1 ] == s[ i ] ) j++;
        next[ i++ ] = j;
    }
}

bool check( char *a, char *b )
{
    int next[ 70 ], i = 0, j = -1, len = strlen( b );
    getnext( b, next );
    while ( a[ i ] )
    {
        while ( j >= 0 && b[ j + 1 ] != a[ i ] ) j = next[ j ];
        if ( b[ j + 1 ] == a[ i ] ) j++;
        if ( j == len - 1 ) return true;
        i++;
    }
    return false;
}

int getpreffix( char *a, char *b )
{
    int i = 0, j = -1, next[ 70 ], lena = strlen( a ), lenb = strlen( b );
//    if ( check( b, a ) ) return 0;
    getnext( b, next );
    while ( a[ i ] )
    {
        while ( j >= 0 && b[ j + 1 ] != a[ i ] ) j = next[ j ];
        if ( b[ j + 1 ] == a[ i ] ) j++;
        i++;
    }
//    printf("!\n");
    return lena - j - 1;
}

void rev( char *s )
{
    int i, len = strlen( s );
    char t;
    for ( i = 0; i < len / 2; i++ )
    {
        t = s[ i ];
        s[ i ] = s[ len - i - 1 ];
        s[ len - i - 1 ] = t;
    }
}

char num[ 16 ][ 70 ];
int n, d[ 16 ][ 16 ], f[ 1 << 16 ][ 16 ], pi[ 1 << 16 ][ 16 ];

void init( )
{
    int i, j;
    long long t;
    for ( i = 0; i < n; i++ )
    {
        scanf("%I64d", &t);
        j = 0;
        if ( t == 0 )
        {
            num[ i ][ 0 ] = '0';
            num[ i ][ 1 ] = 0;
            continue;
        }
        while ( t )
        {
            num[ i ][ j++ ] = t % 2 + '0';
            t /= 2;
        }
        num[ i ][ j ] = 0;
        rev( num[ i ] );
    }
    for ( i = 0; i < n; i++ )
    {
        for ( j = 0; j < n; j++ )
        {
            if ( i == j ) continue;
            if ( check( num[ j ], num[ i ] ) )
                break;
        }
        if ( j < n )
        {
            for ( j = i; j < n - 1; j++ )
                strcpy( num[ j ], num[ j + 1 ] );
            n--; i--;
        }
    }
    for ( i = 0; i < n; i++ )
        for ( j = 0; j < n; j++ )
        {
            if ( i == j ) continue;
            d[ i ][ j ] = getpreffix( num[ i ], num[ j ] );
//            printf("%s %s %d\n", num[ i ], num[ j ], d[ i ][ j ]);
        }
}

void work( )
{
    int i, j, k, p, minn = 1000000000, mp, t;
    long long ans = 0;
    for ( i = 1; i < ( 1 << n ); i++ )
    {
        for ( j = 0; j < n; j++ )
            if ( ( 1 << j ) & i )
            {
                f[ i ][ j ] = 1000000000;
                p = i ^ ( 1 << j );
                if ( p == 0 )
                {
                    f[ i ][ j ] = strlen( num[ j ] );
                    pi[ i ][ j ] = -1;
                }
                else
                    for ( k = 0; k < n; k++ )
                        if ( ( 1 << k ) & p )
                        {
                            if ( f[ i ][ j ] > f[ p ][ k ] + d[ j ][ k ] )
                            {
                                f[ i ][ j ] = f[ p ][ k ] + d[ j ][ k ];
                                pi[ i ][ j ] = k;
                            }
                            else
                                if ( f[ i ][ j ] == f[ p ][ k ] + d[ j ][ k ] )
                                {
//                                    if ( i == 14 && j == 2 )
//                                        printf("!%d %d %d %d\n", i, j, k, pi[ i ][ j ]);
                                    if ( strcmp( num[ k ] + strlen( num[ j ] ) - d[ j ][ k ], num[ pi[ i ][ j ] ] + strlen( num[ j ] ) - d[ j ][ pi[ i ][ j ] ] ) < 0 )
                                        pi[ i ][ j ] = k;
                                }
                        }
            }
    }
    for ( i = 0; i < n; i++ )
    {
        if ( minn > f[ ( 1 << n ) - 1 ][ i ] )
        {
            minn = f[ ( 1 << n ) - 1 ][ i ];
            mp = i;
        }
        else
            if ( minn == f[ ( 1 << n ) - 1 ][ i ] )
                if ( strcmp( num[ i ], num[ mp ] ) < 0 )
                    mp = i;
    }
    p = ( 1 << n ) - 1;
    while ( pi[ p ][ mp ] != -1 )
    {
    //    printf("%d %d %d\n", p, mp, pi[ p ][ mp ]);
//        for ( i = 0; i < 1000000000; i++ );
        for ( i = 0; i < d[ mp ][ pi[ p ][ mp ] ]; i++ )
        {
            ans = ( ans * 2 + num[ mp ][ i ] - '0' ) % 1000000009;
    //        printf("%c", num[ mp ][ i ]);
        }
        t = p;
        p ^= ( 1 << mp );
        mp = pi[ t ][ mp ];
    }
    for ( i = 0; i < strlen( num[ mp ] ); i++ )
        ans = ( ans * 2 + num[ mp ][ i ] - '0' ) % 1000000009;
    //printf("%s\n%d %d %d\n", num[ mp ], minn, d[ 0 ][ 1 ], d[ 1 ][ 0 ]);
    printf("%I64d\n", ans);
}

int main( )
{
    while ( scanf("%d", &n) != EOF )
    {
        init( );
        work( );
    }
    return 0;
}
